1. Field of the Invention
The present invention relates generally to video encoding. More particularly, the present invention relates to a method and apparatus for VLC encoding in a video encoding system.
2. Description of the Related Art
Video compression is used in many current and emerging products, such as digital television set-top boxes (STBs), high definition television (HDTV) decoders, digital versatile disk (DVD) players, BLU-RAY disc players, digital camcorders, personal computers, and the like. Without video compression, digital video content can be extremely large, making it difficult or even impossible for the digital video content to be efficiently stored, transmitted, or viewed. There are numerous video coding methods that compress digital video content. Consequently, video coding standards have been developed to standardize the various video coding methods so that the compressed digital video content is rendered in formats that a majority of video decoders can recognize. For example, the Motion Picture Experts Group (MPEG) and International Telecommunication Union (ITU-T) have developed video coding standards that are in wide use. Examples of these standards include the MPEG-1, MPEG-2 (ITU-T H.262), MPEG-4, ITU-T H.261, and ITU-T H.263 standards.
Video compression, such as MPEG, processes input video information using block-based frequency transform coding (e.g., discrete cosine transform (DCT)) and motion-compensated prediction to produce frequency coefficients and motion vectors. Blocks of frequency coefficients are quantized and scanned in a defined scan order to produce a serial stream of frequency coefficients. The frequency coefficients, along with the motion vectors, are then processed using variable length code (VLC) encoding to produce an encoded video stream. VLC is a coding mechanism that assigns shorter code-words to frequent events, and longer code-words to less frequent events.
Notably, blocks of frequency coefficients typically include one or more non-zero coefficients and many zero-valued coefficients. When scanned, the frequency coefficients result non-zero coefficients separated by a sequence of zero coefficients. In MPEG terms, a “run” is defined as the number of zero-valued coefficients preceding a non-zero coefficient in the scan-order. A “level” is defined as the absolute value of the non-zero coefficient that occurs after the run. A VLC codeword is generated for each run and level combination. In MPEG, a run value can range between 0 and 63 and a level can range between 1 and 2047. MPEG standards specifically define some VLC codewords for run/level combinations that statistically occur frequently (e.g., MPEG-2 defines 113 VLC codewords for particular run/level combinations). For run/level combinations not having specifically defined codewords, the VLC codeword is a fixed codeword including a concatenation of a defined escape sequence, the run, and the level.
In some applications, such as in digital camcorders and personal computers, video compression is performed at least partially using processor-based encoding algorithms. For example, VLC encoding may be performed using a processor that executes instructions. Processor-based encoding algorithms typically employ VLC encoding using lookup tables. For example, FIG. 1 depicts a typical MPEG-2 VLC encoding algorithm. At step 102, a run and level are determined. At step 104, a determination is made whether the run is greater than a maximum run. In MPEG-2, specific VLC codewords are provided for runs between 0 and 31. Any run value greater than 31 is coded using the escape code. Thus, if the run is greater than the maximum run, the method 100 proceeds to step 106, where the escape code is generated. Otherwise, the method 100 proceeds to step 108, where the run is used to query a lookup table to obtain a maximum level for the run. MPEG-2 defines different maximum level values depending on the value of the run. At step 110, a determination is made whether the level is greater than the maximum level for the run. If so, the method 100 proceeds to step 106, where the escape code is generated. Otherwise, the method 100 proceeds to step 112. At step 112, a VLC codeword is selected by first selecting a lookup table corresponding to the run (there are multiple lookup tables, one for each run value), and then querying the selected lookup table with the level value to get the VLC codeword.
The problem with the VLC encoding method in FIG. 1 is that the method requires a processor to perform three load instructions: one load instruction for obtaining the maximum level at step 108, and two load instructions for selecting the lookup table for the run and for loading the VLC codeword given the level at step 112. In a typical processor environment, a load instruction may take two clock cycles, thus requiring six clock cycles for the three load instructions. To illustrate the problem, assume standard definition (SD) video of 720×480 pixels at 30 frames per second with an average of 50% non-zero coefficients and being represented in 4:2:0 chrominance format. Since there are 720×480×1.5×30×50%=7,776,000 coefficients, the processor will require 7,776,000×6=46,656,000 clock cycles just for the load instructions in VLC encoding one second of video. Note the factor of 1.5 is due to the 4:2:0 chrominance format and is even higher for other chrominance formats (e.g., 4:2:2 or 4:4:4). Thus, the VLC encoding method in FIG. 1 exhibits a high cost in terms of processor cycles and is inefficient.
Accordingly, there exists a need in the art for a method and apparatus for VLC encoding in a video encoding system that reduces the number of required load instructions.